import com.sun.xml.internal.bind.v2.model.annotation.Quick;
import sun.text.normalizer.NormalizerBase;

import java.util.Arrays;
import java.util.Scanner;

//import static com.sun.jmx.snmp.agent.SnmpMibNode.QuickSort;

public class test {
    public static void transform(int[]arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i]=arr[i]*2;
        }

    }
public static int[] fun1(int []arr){
        int left=0;
        int right=arr.length-1;
        while(left<=right) {
            if(arr[left]%2==0){//奇数放偶数前
                if(arr[right]%2!=0) {//右边的数是奇数
                    int tmp=arr[left];
                    arr[left]=arr[right];
                    arr[right]=tmp;
                    right--;
                    left++;
                } else{//否则右边的数前移
                    right--;
                }
            } else{
                left++;
            }
        }
    return arr;
}
public static int fun3(int[]arr,int n){
        //二分查找
    int left=0;
    int right=arr.length-1;
    int mid=0;
    while(left<=right) {
            mid=(left+right)/2;
        if(arr[mid]<n) {
            left=mid+1;
        } else if(arr[mid]>n) {
            right=mid-1;
        } else{
            return mid;
        }
    }
    return -1;
}
public static void fun4(int[]arr) {

    for (int i = 0; i < arr.length-1; i++) {
        for (int j = 0; j <arr.length-1-i ; j++) {
            if(arr[j]>arr[j+1]) {
                int tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
            }
        }
    }
}
public static void fun5(int[]arr,int target) {

    for (int i = 0; i <arr.length ; i++) {
        for (int j = i+1; j <arr.length ; j++) {
            if(arr[i]+arr[j]==target){
                System.out.println(i+""+j);
                return;
            }
        }
    }
}
    public static void fun7(int[]arr) {
        //异或
        int i=0;
        int j=0;
        for ( j = 0; j <arr.length ; j++) {
            i^=arr[j];
        }
        //分成两类
        int a=0;//用来计算位数
        int sz=arr.length-1;
        for ( j = 0; j <arr.length ; j++) {
            if(((i>>j)&1)==1) {
                break;
            }
        }
      int p1=0;
        int p2=0;
        for (int k = 0; k <arr.length ; k++) {
            if(((arr[k]>>j)&1)==1) {
                p1^=arr[k];
            } else{
                p2^=arr[k];
            }
        }
        System.out.println(p1+" "+p2);

        //return i;
    }
    public static int fun8(int []arr) {
        //方法一桶排
        //方法二先排序，再根据那个连续次数最多，并且记录当前连续次数最多的元素的值
        int[] p=new int[1000000];
        for (int i = 0; i <arr.length ; i++) {
            int tmp=arr[i];
            p[tmp]=p[tmp]+1;
        }
        for (int i = 0; i < 1000000; i++) {
            if(p[i]>arr.length/2) {
                return i;
            }
        }
        return -1;
    }
public static int fun9(int[]arr) {
        fun4(arr);//前面的冒泡排序
        int max=0;//记录最长的相同元素
        int count=1;
        int p=0;//记录相同元素的值
    for (int i = 0; i <arr.length-1 ; i++) {
        int j=i;
        while((j+1<arr.length)&&(arr[j]==arr[j+1])) {
            count++;
            p=arr[j];
            j++;
        }//1 1 1 2 2 2 2 2
        if(max<count) {
            max=count;
            p=arr[i];
        }
        count=1;
    }
    if(max>arr.length/2) {
        return p;
        } else {
        return -1;
        }
    }

    public static boolean fun10(int []arr) {
        int p1=0;//用于记录连续的奇数的个数
        int p2=0;//
        for (int i = 0; i <arr.length ; i++) {
            if(arr[i]%2!=0) {
                p1++;
            } else {
                p1=0;
            } if(p1==3) {
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        //存在连续三个奇数的数组
        int []arr={1,1,2,2,1,2,3,1,1,1};
        boolean p=fun10(arr);
        System.out.println(p);
    }
    public static void main8(String[] args) {
        int []arr={1 ,1, 1, 2, 2, 2, 2, 2};
        int p=fun9(arr);
        System.out.println(p);
    }
    public static void main7(String[] args) {
        //给定一个大小为 n 的数组，找到其中的多数元素。
        // 多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
        int []arr={3,2,3};
        int p=fun8(arr);
        System.out.println(p);
    }
    public static void main6(String[] args) {
        //给定一个非空整数数组，除了某个元素只出现一次以外，
        // 其余每个元素均出现两次。找出那个只出现了一次的元素。
        int []arr={1,2,3,4,5,5,4,3,1,6};
       fun7(arr);
    }
    public static void main5(String[] args) {
        //输入：nums = [2,7,11,15], target = 9
           int[] arr={1,2,3,4,5,6,7,8,9,10};
            fun5(arr,9);
    }
    public static void main4(String[] args) {
        //给定一个整型数组, 实现冒泡排序(升序排序)
        int []arr={2,4,6,8,10,1,3,5,7,9};
        fun4(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
            int cmp=in.nextInt();
        int []arr={1,2,3,4,5,6,7,8,9,10};
        int p=fun3(arr,cmp);
        System.out.println(p);
    }
    public static void main2(String[] args) {
        //奇数放偶数前
        int []arr={2,4,6,8,10,1,3,5,7,9};
        System.out.println(Arrays.toString(fun1(arr)));
    }
    public static void main1(String[] args) {
        //改变原有数组元素的值
        int []arr={1,2,3,4,5};
        transform(arr);
        System.out.println(Arrays.toString(arr));

    }
}
